Various display devices like computer printers and computer monitors present images with a broad range of colors by forming small spots or picture elements (pixels) using only a limited number of primary colors. The spatial densities and/or size of the pixels for each primary color are adapted to represent a range of colors. For example, many printing devices use cyan, magenta, yellow and possibly black inks to display color images. Many video display devices and computer monitors such as cathode ray tube (CRT) and liquid crystal display (LCD) devices use elements emitting red, green and blue light to display color images.
In one type of presentation, variations in color are obtained using pixels of uniform size by varying the spatial density or separation between pixels for each primary color. In another type of presentation, variations in color are obtained by varying the spatial density of pixels as well as the size of each pixel for each primary color. Although more particular mention is made herein of presentations that vary only pixel density, the present invention may be used with either type of presentation.
Both accuracy and uniformity of perceived color are affected by how the pixels of each primary color are placed. For example, with techniques known as periodic screening, it is well known that slight errors in alignment between regularly-spaced grids of pixels for each primary color will combine to generate moire or interference patterns which produce color variations in areas that are supposed to be of uniform color. Another problem manifests itself as shifts in color as the grids or screens of pixels are displaced relative to one another. These displacements in pixel positions, or registration errors, alter the perceived color. A number of techniques have been developed to minimize these effects.
One technique reduces the visibility of moire patterns by rotating the grid for pixels of one primary color relative to the grid for pixels of another primary color. Generally, as the angle between grids increases, the frequency of the resulting moire increases to a point where the interference pattern is not too visible. Unfortunately, this technique does not work as well for images formed from several primary colors because it is very difficult to choose suitable angles between all of the grids of the several primary colors. Furthermore, it is essentially impossible to apply this technique with devices like computer printers and monitors that are constrained to present pixels at fixed, regularly-spaced positions defined by grids that cannot be rotated relative to one another.
Because of these limitations, other techniques known as stochastic screening have been used with varying degrees of success. These techniques generate pseudo-random distributions of pixels to reduce or eliminate the periodic artifacts resulting from periodic placement of pixels within regularly-spaced grids. In U.S. Pat. No. 5,485,397, for example, a disclosed technique analyzes an image to determine areas of nearly constant color density, divides these areas into smaller segments of nearly constant area, calculates the number of pixels needed for each primary color to achieve the desired pixel density in each segment, and distributes the calculated number of pixels in a pseudo-random manner within each segment. In U.S. Pat. No. 4,876,611, a disclosed technique recursively divides an image into progressively smaller areas and locates pixels of the primary colors in each of these smaller areas in such a way that the correct average pixel density for all primary colors is maintained for larger areas. Unfortunately, these and other stochastic techniques require considerable processing resources to determine how pixels for each primary color should be located and each suffers from visible alterations in color caused by registration errors.
In U.S. Pat. No. 5,394,252, many problems with both periodic screening and stochastic screening are overcome by using both regularly-spaced grids and irregularly-spaced or randomly-spaced grids. Unfortunately, the requirement to use at least one irregularly-spaced grid is incompatible with devices like computer printers and monitors that present pixels at regularly-spaced intervals.